#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

typedef int HeapType;
struct Heap
{
	HeapType* _a = nullptr;
	size_t _size = 0;
	size_t _capacity = 0;
};

void HeapInit(Heap* hp)
{
	hp->_a = nullptr;
	hp->_size = hp->_capacity = 0;
}

size_t HeapSize(Heap* hp)
{
	return hp->_size;
}

bool HeapEmpty(Heap* hp)
{
	return hp->_size == 0;
}
//建大堆
//坑点：如果child是size_t类型：当第一次插入的时候,child为0的时候,下面child-1得到的就是-1 =>由于是无符号类型=>代表整数最大值
//最后导致parent位置计算越界！ 
void AdjustUp(Heap* hp,int child) 
{
	size_t parent = (child - 1) / 2;
	while (parent >= 0)
	{
		if (hp->_a[parent] < hp->_a[child])
		{
			::swap(hp->_a[parent], hp->_a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void AdjustDown(Heap* hp, size_t parent,size_t n)
{
	size_t child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && hp->_a[child + 1] > hp->_a[child])
			child += 1;

		if (hp->_a[parent] < hp->_a[child])
		{
			::swap(hp->_a[parent], hp->_a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* hp,HeapType x)
{
	if (hp->_size == hp->_capacity)
	{
		size_t newcap = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
		cout << "当前容量为：" << hp->_capacity << " 扩容为：" << newcap << endl;
		HeapType* newArr = new HeapType[newcap];
		hp->_capacity = newcap;
		for (int i = 0; i < hp->_size; i++)
			newArr[i] = hp->_a[i];
		delete[] hp->_a;
		hp->_a = newArr;
	}
	hp->_a[hp->_size++] = x;
	AdjustUp(hp,hp->_size-1);
}

void HeapPop(Heap* hp)
{
	assert(!HeapEmpty(hp));
	::swap(hp->_a[0], hp->_a[--hp->_size]);
	AdjustDown(hp, 0, hp->_size);
}

HeapType HeapTop(Heap* hp)
{
	assert(!HeapEmpty(hp));
	return hp->_a[0];
}

void HeapPrint(Heap* hp)
{
	cout << "=====================" << endl;
	for (int i = 0; i < hp->_size; i++)
		cout << hp->_a[i] << " ";
	cout << endl;
	cout << "=====================" << endl;

	cout << endl;
}

//int main()
//{
//	Heap hp;
//	HeapPush(&hp, 0);
//	HeapPrint(&hp);
//	HeapPush(&hp, 1);
//	HeapPrint(&hp);
//	HeapPush(&hp, 2);
//	HeapPrint(&hp);
//	HeapPush(&hp, 3);
//	HeapPrint(&hp);
//	HeapPush(&hp, 4);
//	HeapPrint(&hp);
//	while (!HeapEmpty(&hp))
//	{
//		cout << HeapTop(&hp) << " ";
//		HeapPop(&hp);
//	}
//	return 0;
//}
